package leetcode.pre50;

import java.util.Arrays;

/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
 * <p>
 * 找出 nums 中的三个整数，使得它们的和与 target 最接近。
 * <p>
 * 返回这三个数的和。假定每组输入只存在唯一答案。
 * <p>
 * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
 * <p>
 * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
 * <p>
 * 其余见{@link leetcode.a_总结分布.Code11_N数之和}
 *
 * @date 2019/11/16 0016 上午 11:03
 */
public class Code16_FindThree_三数之和 {


    /**
     * 方式2：排序 + 双指针。时间O(n²),空间O(1)
     * 分析见leetcode https://leetcode-cn.com/problemset/all/?listId=2cktkvj 15.三数之和
     */
    public static int threeSum2(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return -1;
        }
        //先进行排序
        Arrays.sort(nums);
        int left;
        int right;
        //第一个数的位置位index。然后设定p1 = index+1,p2 = nums.length -1。
        //遍历判断是否有满足的数。
        //分别代表最小值，以及最小值的对应的三个元素
        int[] min = {Integer.MAX_VALUE, -1, -1, -1};

        int sum = 0;
        for (int index = 0; index < nums.length - 2; index++) {
            left = index + 1;
            right = nums.length - 1;

            //【注意点1】去重,比如[-1,-1,.....,]之前一轮index = 0，
            // 现在index=1，重复了，要去重
            if (index != 0 && nums[index] == nums[index - 1]) {
                continue;
            }
            //最小的组合已经比target大，后面就更大了
            if((sum = nums[index] + nums[index+1] + nums[index+2] - target) > 0) {
                return min[0] > sum ? sum + target : min[1] + min[2] + min[3];
            }
            //不可用重复的数 ，left要小于right
            while (left < right) {
                sum = nums[index] + nums[left] + nums[right];
                if (Math.abs(sum - target) < min[0]) {
                    min[0] = Math.abs(sum - target);
                    min[1] = nums[index];
                    min[2] = nums[left];
                    min[3] = nums[right];
                }
                if (sum == target) {
                    return target;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return min[1] + min[2] + min[3];
    }

    public static void main(String[] args) {
        int[] nums = {-1,2,1,-4};
        int target = 1;
        System.out.println(threeSum2(nums, target));
    }



}
